package tools;

import java.util.List;
import java.util.Stack;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

import Triangulation.minimalityMetrics.MinimalityMetric;
import datatypes.Edge;
import datatypes.IndexedFaceSet;
import datatypes.Vertex;
import controller.DraftingHint;
import controller.Globals;
import datatypes.list.DoublyLinkedList;
import datatypes.list.Node;

/**
 * 
 * @author markessien, nils
 *
 */
public class FastLMTSkeletonCreator {
	public class Logger {
		public long edgesCheckedForIntersection = 0;
		public int edgesWithoutLocalMinimum = 0;
		public int nonIntersectingEdges = 0;
		public double time;
		public double timePartA = 0;
		public double timePartB = 0;
		public double convexHullTime = 0;
		public double timeGenerateEdges = 0;
		public double timeGenerateTriangles = 0;
	}
	
	private Logger logger = new Logger();
	private MinimalityMetric metric;
	
	public FastLMTSkeletonCreator(MinimalityMetric metric) {
		this.metric = metric;
	}

	public Logger getLogger() {
		return logger;
	}
	/**
	 * The LMT-skeleton is a subgraph of the original graph. It contains all the
	 * edges that are in all possible minimum weight triangulations. After the LMT
     * is found, then the MWT can be calculated
	 * SEE A Large Subgraph of the Minimum Weight Triangulation page294
	 * 
	 * This function calculates the LMT.
	 * 
	 * 
	 * @param points The set of points
	 * @return The list with all edges within the skeleton in them
	 */
	public IndexedFaceSet calculateLMT(IndexedFaceSet set) {
		long start = System.currentTimeMillis();
		long startEdges = System.currentTimeMillis();
		set.generateEdges();
		logger.timeGenerateEdges += ((double)(System.currentTimeMillis() - startEdges))/1000;
		if (set.size() <= 3) {
			set.edgesIn = set.getCandidateEdges();
			return set;
		}
		boolean edgeChanged = false;
		
		
		long startTris = System.currentTimeMillis();
		set.generateTriangles();
		logger.timeGenerateTriangles += ((double)(System.currentTimeMillis() - startTris))/1000;
		System.out.println("Triangle count:" + set.triangleCount());
		
		// This method will look at the list of all potential edges ( set.getEdges() )
		// and it will add all edges that belong to the convex hull to the edgesIn list.
		// The convex hull is always part of any triangulation, and thus its edges are
		// in any minimum triangulation.
		long startCH = System.currentTimeMillis();
		List<Vertex> convexHullPoints = ConvexHullCreator.doJarvisMarch(set);
		
		// edgesIn is a list of edges that have been determined to be in
		// any locally minimal triangulation
		set.edgesIn = ConvexHullCreator.getHullEdges(convexHullPoints, set.getCandidateEdges()); // TODO: may be inefficient...
		
		// Remove convex hull edges from our candidate list
		for (Edge e : set.edgesIn) {
			set.removeEdgeButLeaveTriangles(e);
		}
		logger.convexHullTime += ((double)(System.currentTimeMillis() - startCH))/1000;
		
		do {
			long startA = System.currentTimeMillis();
			edgeChanged = removeNonMinimalEdges(set);
			logger.timePartA += ((double)(System.currentTimeMillis() - startA))/1000;
			
			long startB = System.currentTimeMillis();
			if (reportNonIntersectingEdges(set)) {
				edgeChanged = true;
			}
			logger.timePartB += ((double)(System.currentTimeMillis() - startB))/1000;
		} while (edgeChanged);
		logger.time = ((double)(System.currentTimeMillis() - start))/1000;
		
		System.out.println("Edges checked for intersection: " + logger.edgesCheckedForIntersection);
		System.out.println("Running time: " + logger.time);
		System.out.println("Running time Convex Hull: " + logger.convexHullTime);
		System.out.println("Running time generating edges: " + logger.timeGenerateEdges);
		System.out.println("Running time generating tris: " + logger.timeGenerateTriangles);
		System.out.println("Running time part A: " + logger.timePartA);
		System.out.println("Running time part B: " + logger.timePartB);
		System.out.println("");
		// logger = new Logger();
//		System.out.println("\n***\n  found " + edgesIn.size() + " edges!\n***\n");
		return set;
	}


	/**
	 * @param set
	 * @param edgesIn
	 * @return
	 */
	private boolean reportNonIntersectingEdges(IndexedFaceSet set) {
		boolean edgeChanged = false;
		DoublyLinkedList<Edge> edges = set.getCandidateEdges();
		for (Node<Edge> node : edges.nodeIterable()) {
			Edge edge = node.element;
			// IF e intersects no other edge in candEdges THEN add e to the edgesIn
			boolean intersects = false;
			Node<Edge> intersectingEdgeNode = edge.getFirstEdgeToCheckForIntersection();
			if (intersectingEdgeNode == null) {
				intersectingEdgeNode = set.getCandidateEdges().headNode();
			}
			
			while (intersectingEdgeNode != null) {
				
				Edge otherEdge = intersectingEdgeNode.element;
				logger.edgesCheckedForIntersection++;
								
				if ( ! edge.isAdjacentToEdge(otherEdge)) {
					// Using negative precision value to prevent adjacent edges
					// from being detected as intersecting edges
					if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
						intersects = true;
						edge.setFirstEdgeToCheckForIntersection(intersectingEdgeNode);
						break;
					}
				}
				intersectingEdgeNode = intersectingEdgeNode.next;
			}
			
			if (intersects == false) {
				edge.status = DraftingHint.IN;
					set.edgesIn.add(edge);
					
					/* TODO: Under certain circumstances triangles may be removed too.
					 * Maybe that would an improvement? Investigate!!!
					 */
					set.removeEdgeButLeaveTriangles(edge); // remove edge from candEdges. Not specified in the paper
					edgeChanged = true;
					logger.nonIntersectingEdges++;
			}
		}
		return edgeChanged;
	}
	
	
//	/**
//	 * @param set
//	 * @param edgesIn
//	 * @return
//	 */
//	private boolean reportNonIntersectingEdgesConcurrently(IndexedFaceSet set) {
//		boolean edgeChanged = false;
//		DoublyLinkedList<Edge> edges = set.getCandidateEdges();
//		Stack<Future<Boolean>> futures = new Stack<Future<Boolean>>();
//		for (Node<Edge> node : edges.nodeIterable()) {
//			
//			// IF e intersects no other edge in candEdges THEN add e to the edgesIn
//			futures.push(intersects(node, set));
//		}
//		for (Future<Boolean> future : futures) {
//			try {
//				if (future.get()) {
//					edgeChanged = true;
//					break;
//				}
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			} catch (ExecutionException e) {
//				e.printStackTrace();
//			}
//		}
//		return edgeChanged;
//	}
//	
//	private Future<Boolean> intersects(final Node<Edge> node, final IndexedFaceSet set) {
//		ExecutorService executer = Globals.mainExecutor;
//		Future<Boolean> future = executer.submit(new Callable<Boolean>() {
//
//			@Override
//			public Boolean call() throws Exception {
//				boolean intersects = false;
//				Edge edge = node.element;
//				Node<Edge> intersectingEdgeNode;
//				List<Edge> candidateEdges = set.getCandidateEdges();
//				synchronized (candidateEdges) {
//					intersectingEdgeNode = edge.getFirstEdgeToCheckForIntersection();
//					if (intersectingEdgeNode == null) {
//						intersectingEdgeNode = set.getCandidateEdges().headNode();
//					}
//				}
//				
//				
//				while (intersectingEdgeNode != null) {
//					
//					Edge otherEdge = intersectingEdgeNode.element;
//					logger.edgesCheckedForIntersection++;
//									
//					if ( ! edge.isAdjacentToEdge(otherEdge)) {
//						// Using negative precision value to prevent adjacent edges
//						// from being detected as intersecting edges
//						if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
//							intersects = true;
//							edge.setFirstEdgeToCheckForIntersection(intersectingEdgeNode);
//							break;
//						}
//					}
//					synchronized (candidateEdges) {
//						intersectingEdgeNode = intersectingEdgeNode.next;
//					}
//				}
//				
//				if (intersects == false) {
//					edge.status = DraftingHint.IN;
//						set.edgesIn.add(edge);
//						
//						/* TODO: Under certain circumstances triangles may be removed too.
//						 * Maybe that would an improvement? Investigate!!!
//						 */
//						synchronized (candidateEdges) {
//							set.removeEdgeButLeaveTriangles(edge); // remove edge from candEdges. Not specified in the paper
//						}
//						
//						logger.nonIntersectingEdges++;
//				}
//				return false;
//			}
//			
//		});
//		return future;
//	}


	/**
	 * @param set
	 * @return
	 */
	private boolean removeNonMinimalEdges(IndexedFaceSet set) {
		boolean edgeChanged = false;
		for (Edge edge : set.getCandidateEdges()) {
			if ( ! edge.isDiagonalOfQuadrilateral() ) {
				set.removeEdge(edge);
				edgeChanged = true;
				continue;
			}
			
			// If we find that this edge is not the local minimum for any possible
			// quadrilateral, this edge cannot be an element of an MWT. Hence we can
			// remove it from the candidates.
			if ( ! metric.localMinimumExistsForEdge(edge, set) ) {
				
				set.removeEdge(edge);
				edgeChanged = true;
				logger.edgesWithoutLocalMinimum++;
			} else {
				edge.status = DraftingHint.LOCALLY_MINIMAL;
			}
		}	
		return edgeChanged;
	}
	
	public String getMetricName() {
		return metric.getName();
	}
}
